package lhc.alg.top100;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * description: 二叉树遍历 后序遍历的迭代解法
 * author: hongchen.liao
 * date:  2022/8/1
 */
public class _145_Binary_Tree_Postorder_Traversal {



     //Definition for a binary tree node.
     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if(root == null){
                return res;
            }
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode prev = null;
            while(root != null || !stack.isEmpty()){
                while(root != null){
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if(root.right == null || root.right == prev){
                    res.add(root.val);
                    prev = root;
                    root = null;
                }else{
                    stack.push(root);
                    root = root.right;
                }
            }
            return res;
        }
    }

}
